/*!
 * \file RepSearchTree.h
 *
 * \date Nov 13, 2014
 * \author correa
 */
#ifndef REPSEARCHTREE_H_
#define REPSEARCHTREE_H_

#include <cstdlib>

using namespace std;

enum struct TipoPareja { _IDENT, _CONNECT, _FIXASREP, _FIXASNOREP, _ROOT };

template <class T>
class RepSearchTree : public FactoryDesigualdad, public FactoryDesigualdadArray<T>
{
	VertexSet					_vecindadI;
	VertexSet					_vecindadII;
	VertexSet					_novecinosI;
	VertexSet					_novecinosII;
	list<DesigualdadArray<T> *>	_desigualdades;

protected:
	class Pareja
	{
		friend class RepSearchTree;

	private:
		int			_r;
		int 		_v;
		Grafo&		_actual;
		Grafo *		_grafo;
		TipoPareja	_tipo;
		Pareja *	_right;
		Pareja *	_left;
		Pareja *	_parent;
		VertexSet *	_fixedone;
		VertexSet *	_fixedzero;
		VertexSet *	_pseudofixed;

		Pareja(Grafo& g) : _r(g.getN()), _v(g.getN()), _actual(g), _grafo(new Grafo(g)), _tipo(TipoPareja::_ROOT), _right(NULL), _left(NULL), _parent(NULL)
		{
			_fixedone = new VertexSet(g.getN());
			_fixedzero = new VertexSet(g.getN());
			_pseudofixed = new VertexSet(g.getN());
			VertexSet vecinos(g.getN());
			for (int v = 0; v < g.getN(); v++) {
				vecinos.copyCompl(g.vecinos(v));
				if (vecinos.least() >= v)
					_fixedone->add(v);
			}
		};

	public:
		Pareja(int r, int v, Pareja * p, TipoPareja t) : _r(r), _v(v), _actual(p->_actual), _grafo(p->_grafo), _tipo(t), _right(NULL), _left(NULL), _parent(p)
		{
			if (_parent->_right == NULL)
				_parent->_right = this;
			else
				_parent->_left = this;
			switch (t) {
			case TipoPareja::_CONNECT:
				if (_parent->_fixedone->contains(r))
					_fixedone = _parent->_fixedone;
				else
				{
					_fixedone = new VertexSet(*_parent->_fixedone);
					_fixedone->add(r);
				}
				_pseudofixed = _parent->_pseudofixed;
				_fixedzero = _parent->_fixedzero;
				break;
			case TipoPareja::_IDENT:
				if (_parent->_fixedone->contains(r))
				{
					if (!_parent->_fixedzero->contains(v))
					{
						_fixedzero = new VertexSet(*_parent->_fixedzero);
						_fixedzero->add(v);
					}
					else
						_fixedzero = _parent->_fixedzero;
					if (!_parent->_pseudofixed->contains(v))
						_pseudofixed = _parent->_pseudofixed;
					else
					{
						_pseudofixed = new VertexSet(*_parent->_pseudofixed);
						_pseudofixed->remove(v);
					}

				}
				else {
					if (_parent->_pseudofixed->contains(r))
						_pseudofixed = _parent->_pseudofixed;
					else
					{
						_pseudofixed = new VertexSet(*_parent->_pseudofixed);
						_pseudofixed->add(r);
					}
					_fixedzero = _parent->_fixedzero;
				}
				_fixedone = _parent->_fixedone;
				break;
			case TipoPareja::_FIXASREP:
				if (!_parent->_fixedone->contains(r))
				{
					_fixedone = new VertexSet(*_parent->_fixedone);
					_fixedone->add(r);
				}
				else
					_fixedone = _parent->_fixedone;
				if (!_parent->_pseudofixed->contains(r))
					_pseudofixed = _parent->_pseudofixed;
				else
				{
					_pseudofixed = new VertexSet(*_parent->_pseudofixed);
					_pseudofixed->remove(r);
				}
				_fixedzero = _parent->_fixedzero;
				break;
			case TipoPareja::_FIXASNOREP:
				if (!_parent->_fixedzero->contains(r))
				{
					_fixedzero = new VertexSet(*_parent->_fixedzero);
					_fixedzero->add(r);
				}
				else
					_fixedzero = _parent->_fixedzero;
				if (!_parent->_pseudofixed->contains(r))
					_pseudofixed = _parent->_pseudofixed;
				else
				{
					_pseudofixed = new VertexSet(*_parent->_pseudofixed);
					_pseudofixed->remove(r);
				}
				_fixedone = _parent->_fixedone;
				break;
			default:
				break;
			}
		};
		~Pareja()
		{
			if (_parent != NULL)
			{
				if (_fixedone != _parent->_fixedone)
					delete _fixedone;
				else
				{
					if (_fixedzero != _parent->_fixedzero)
						delete _fixedzero;
					if (_pseudofixed != _parent->_pseudofixed)
						delete _pseudofixed;
				}
				if (_parent->_parent != NULL && (_parent->_right == NULL || _parent->_left == NULL))
					delete _parent;
				else if (_parent->_right == this)
					_parent->_right = NULL;
				else
					_parent->_left = NULL;
			}
			else
			{
				delete _grafo;
				delete _fixedone;
				delete _fixedzero;
				delete _pseudofixed;
			}
		};

		bool hayHijos() { return (_right != NULL || _left != NULL); };
		TipoPareja getTipo() { return _tipo; };
		void print() {
			cout << "(" << _r << "," << _v << ",";
			switch (_tipo) {
				case TipoPareja::_CONNECT:
					cout << "CONNECT";
					break;
				case TipoPareja::_IDENT:
					cout << "IDENT";
					break;
				case TipoPareja::_ROOT:
					cout << "ROOT";
					break;
				case TipoPareja::_FIXASNOREP:
					cout << "NOREP";
					break;
				case TipoPareja::_FIXASREP:
					cout << "REP";
					break;
				default:
					break;
			}
			cout << ")" << endl; if (_parent != NULL) _parent->print();
		};
	};

	Pareja		_root;
	Pareja *	_actual;

	virtual DesigualdadArray<T> * newDesigualdadArray() = 0;
	virtual DesigualdadArray<T> * newDesigualdadArray(const DesigualdadArray<T>& otra) = 0;
	void configGrafo(Pareja * p);

private:
	bool estaFijoComoRep(int v, Pareja * p);
	bool estaFijoComoNoRep(int v, Pareja * p);
	bool estaPseudoFijo(int v, Pareja * p);
	bool VecindadDefinitiva(int v, Pareja * p, VertexSet& set);
	bool VecindadSiRep(int v, Pareja * p, VertexSet& set);

public:
	RepSearchTree(Grafo& g);
	virtual ~RepSearchTree();
	list<DesigualdadArray<T> *>& dominadosEnDifinitivo(int v, Pareja * p);
	list<DesigualdadArray<T> *>& dominadosSiRep(int v, Pareja * p);
};

template <class T>
inline RepSearchTree<T>::RepSearchTree(Grafo& g) : _root(g), _actual(&_root), _vecindadI(g.getN()), _vecindadII(g.getN()), _novecinosI(g.getN()), _novecinosII(g.getN()), _desigualdades()
{
}

template <class T>
inline RepSearchTree<T>::~RepSearchTree()
{
}

template <class T>
inline bool RepSearchTree<T>::estaFijoComoRep(int v, Pareja * p)
{
	return p->_fixedone->contains(v);
}

template <class T>
inline bool RepSearchTree<T>::estaFijoComoNoRep(int v, Pareja * p)
{
	return p->_fixedzero->contains(v);
}

template <class T>
inline bool RepSearchTree<T>::estaPseudoFijo(int v, Pareja * p)
{
	return p->_pseudofixed->contains(v);
}

template <class T>
inline bool RepSearchTree<T>::VecindadDefinitiva(int v, Pareja * pareja, VertexSet& set)
{
	set.addAll(_root._grafo->vecinos(v));
	bool ret = false;

	while (pareja != NULL) {
		if (pareja->_tipo == TipoPareja::_CONNECT)
		{
			if (pareja->_r == v)
			{
				ret = ret || !set.contains(pareja->_v);
				set.add(pareja->_v);
			}
			else if (pareja->_v == v)
			{
				ret = ret || !set.contains(pareja->_r);
				set.add(pareja->_r);
			}
		}
		else if (pareja->_tipo == TipoPareja::_IDENT)
		{
			if (pareja->_r == v && estaFijoComoRep(v, pareja->_parent))
				ret = ret || VecindadDefinitiva(pareja->_v, pareja->_parent, set);
			else if (pareja->_v == v && estaFijoComoRep(pareja->_r, pareja->_parent))
				ret = ret || VecindadDefinitiva(pareja->_r, pareja->_parent, set);
		}

		pareja = pareja->_parent;
	}

	return ret;
}

template <class T>
inline bool RepSearchTree<T>::VecindadSiRep(int v, Pareja * pareja, VertexSet& set)
{
	set.addAll(_root._grafo->vecinos(v));
	bool ret = false;

	while (pareja != NULL) {
		if (pareja->_tipo == TipoPareja::_CONNECT)
		{
			if (pareja->_r == v)
			{
				ret = ret || !set.contains(pareja->_v);
				set.add(pareja->_v);
			}
		}
		else if (pareja->_tipo == TipoPareja::_IDENT && pareja->_r == v)
			ret = ret || VecindadDefinitiva(pareja->_v, pareja->_parent, set);
		pareja = pareja->_parent;
	}

	return ret;
}

template <class T>
inline list<DesigualdadArray<T> *>& RepSearchTree<T>::dominadosEnDifinitivo(int v, Pareja * p)
{
	_desigualdades.clear();
	if (v == 0)
		return _desigualdades;

	_vecindadI.removeAll();
	if (VecindadDefinitiva(v, p, _vecindadI))
	{
//		_dominados.removeAll();
		_novecinosI.copyCompl(_vecindadI);
		_novecinosI.remove(v);
		VertexSetIterator it = _novecinosI.begin();
		for (; it != _novecinosI.end() && *it < v; ++it)
		{
			_vecindadII.removeAll();
			VecindadDefinitiva(*it, p, _vecindadII);
			if (_vecindadII.isSubsetOf(_vecindadI))
			{
//				_dominados.add(*it);
//				cout << v << " (";
//				if (!estaFijoComoRep(v, p))
//					if (estaFijoComoNoRep(v, p))
//						cout << "ZERO ";
//					else
//						cout << "NO ";
//				cout << "FIJO) domina " << *it << endl;
//				cout << "Vecindad definitiva de " << v << ": ";
//				_vecindadI.print();
//				cout << "Vecindad definitiva de " << *it << ": ";
//				_vecindadII.print();

				int w = *it;
				DesigualdadArray<T> * ret;

				_novecinosII.copyCompl(_vecindadII);
				_novecinosII.removeAll(_vecindadI);
				_novecinosII.remove(w);

				VertexSetIterator r = _novecinosII.begin();
				for (; r != _novecinosII.end() && *r < w; ++r)
				{
					ret = newDesigualdadArray();
					(*ret)[*r].setCoeficiente(w, 1);
					(*ret)[*r].setCoeficiente(v, -1);
					ret->setRHS(0);
					_desigualdades.push_back(ret);

					ret = newDesigualdadArray();
					(*ret)[*r].setCoeficiente(w, -1);
					(*ret)[*r].setCoeficiente(v, 1);
					ret->setRHS(0);
					_desigualdades.push_back(ret);
				}

				ret = newDesigualdadArray();
				for (; r != _novecinosII.end() && *r > w && *r < v; ++r)
					(*ret)[*r].setCoeficiente(v, 1);
				(*ret)[v].setCoeficiente(v, -1);
				ret->setRHS(-1);
				_desigualdades.push_back(ret);
			}
		}
		for (; it != _novecinosI.end(); ++it)
			if (!estaFijoComoRep(*it, p))
			{
				_vecindadII.removeAll();
				VecindadDefinitiva(*it, p, _vecindadII);
				if (_vecindadII.isSubsetOf(_vecindadI))
				{
					//				_dominados.add(*it);
//					cout << v << " (";
//					if (!estaFijoComoRep(v, p))
//						cout << "NO ";
//					cout << "FIJO) domina " << *it << endl;
//					cout << "Vecindad definitiva de " << v << ": ";
//					_vecindadI.print();
//					cout << "Vecindad definitiva de " << *it << ": ";
//					_vecindadII.print();

					int w = *it;
					DesigualdadArray<T> * ret;

					_novecinosII.copyCompl(_vecindadII);
					_novecinosII.remove(w);

					if (_novecinosII.least() < v)
					{
						ret = newDesigualdadArray();
						for (VertexSetIterator r = _novecinosII.begin(); r != _novecinosII.end() && *r < v; ++r)
							(*ret)[*r].setCoeficiente(w, 1);
						ret->setRHS(0);
						_desigualdades.push_back(ret);
					}
				}
			}
	}

	return _desigualdades;
}

template <class T>
inline list<DesigualdadArray<T> *>& RepSearchTree<T>::dominadosSiRep(int v, Pareja * p)
{
	_desigualdades.clear();
	if (estaFijoComoNoRep(v, p) || estaFijoComoRep(v, p))
		return dominadosEnDifinitivo(v, p);
	return _desigualdades;
}

template <class T>
inline void RepSearchTree<T>::configGrafo(Pareja * p)
{
	if (_actual == p)
		return;

	p->_actual.copy(*p->_grafo);
	while (p != NULL)
	{
		switch (p->_tipo) {
		case TipoPareja::_CONNECT:
			p->_actual.addArista(p->_r, p->_v);
			break;
		case TipoPareja::_IDENT:
			p->_actual.addVecinos(p->_r, p->_actual.vecinos(p->_v));
			p->_actual.addVecinos(p->_v, p->_actual.vecinos(p->_r));
			break;
		default:
			break;
		}
		p = p->_parent;
	}
	_actual = p;
}

#endif /* REPSEARCHTREE_H_ */
